The problem can be found at the following link: Question Link
To find the length of the longest repeating subsequence in a given string, I used a recursive approach with memoization.
- In function
maxSub
that takes the starting indicesi
andj
, the length of the stringn
, the strings
, and a memoization tabledp
. - If
i
orj
reaches the end of the stringn
, return 0. - If the subproblem has already been computed and stored in
dp[i][j]
, return the result fromdp
. - If the characters at indices
i
andj
are equal andi
is not equal toj
, then the current characters contribute to the length of the repeating subsequence. Recursively callmaxSub
withi + 1
andj + 1
to find the length of the next repeating subsequence. - If the characters at indices
i
andj
are not equal, then one of them cannot be part of the repeating subsequence. Recursively callmaxSub
with eitheri
andj + 1
ori + 1
andj
, and take the maximum of the two results. - Store the computed result in
dp[i][j]
.
- Time Complexity:
O(n^2)
due to the nested recursive calls and the memoization table. - Auxiliary Space Complexity:
O(n^2)
as we use a memoization table of size n * n.
class Solution {
public:
int maxSub(int i, int j, int n, string& s, vector<vector<int>>& dp) {
if (i == n || j == n)
return 0;
if (dp[i][j] != -1)
return dp[i][j];
if (i != j && s[i] == s[j]) {
dp[i][j] = 1 + maxSub(i + 1, j + 1, n, s, dp);
} else {
dp[i][j] = maxSub(i, j + 1, n, s, dp);
dp[i][j] = max(dp[i][j], maxSub(i + 1, j, n, s, dp));
}
return dp[i][j];
}
int LongestRepeatingSubsequence(string str) {
int n = str.size();
vector<vector<int>> dp(n, vector<int>(n, -1));
return maxSub(0, 0, n, str, dp);
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.